/**
 * XorOrderDiv2
 * 
 * difficuty: 1000
 * 
 * Statement:

Welcome to the Festival of Binary Numbers! 
The festival will last for 2^m days. 
The days are numbered 0 through 2^m - 1. 
On each day of the festival there is a single race. 
There are n contestants, numbered 0 through n-1. 
Each contestant takes part in all 2^m races.
 
You are given the int m and a int[] a with n elements. 
For each i, the skill level of contestant i is a[i]. 
All a[i] are integers between 0 and 2^m - 1, inclusive. 
Additionally, all a[i] are distinct.
 
For each i and j, the time needed by contestant i to finish the race on day j can be computed as (a[i] xor j). 
Note that on each day the contestants' times will all be distinct. 
After each race the contestants are ordered according to the time they needed, starting with the fastest one. 
Contestant who places x-th (counting from zero) will get x^2 penalty points. 
(I.e., starting from the winner of the race, the contestants get 0, 1, 4, 9, 16, ... penalty points.) 
For each i, let p[i] be the total number of penalty points contestant i receives in the 2^m races.
 
Compute and return the long[] p.

 * 
 * point:
 *   m = 0, 0b0001
 *   m = 1, 0b0010
 *   n < 2^m
 *   
 *   
 *   ti0 = ai xor 0 = ai
 *   ti1 = ai xor 1 = ai (-1/0)
 *   ...
 *   tix = ai xor x = 0
 *   ...
 *   tie = ai xor 2^m-1 = ^ai
 *   
 */
package org.yuwgle.srm.r697.d2;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class XorOrderDiv2 {
	class Contestant implements Comparable<Contestant>{
		int index;
		int skill;
		int point;
		int lasttime;
		@Override
		public int compareTo(Contestant o) {
			return this.lasttime - o.lasttime;
		}
		
		@Override
		public String toString() {
			return skill+" -> " + point + " -> " + lasttime;
		}
	}
	
	public long[] getExpectation(int m, int[] a) {
		List<Contestant> conts = new ArrayList<>();
		for (int i = 0; i < a.length; i++) {
			Contestant e = new Contestant();
			e.index = i;
			e.skill = a[i];
			conts.add(e);
		}
		
		long maxday = (long)Math.pow(2, m);
		for (int j = 0; j < maxday; j++) {
			for (Contestant c : conts) {
				c.lasttime = c.skill ^ j;
			}
			
			Collections.sort(conts);
			
			for (int r = 0; r < a.length; r++) {
				conts.get(r).point += r*r;
			}
			System.out.println("loop:"+j + "  array:"+ conts);
		}
		
		long[] p = new long[a.length];
		
		for (Contestant c : conts) {
			p[c.index] = c.point;
		}
		
		return p;
	}
	
	public static void main(String[] args) {
		int m;
		int[] a;
		long[] ret;
		XorOrderDiv2 x = new XorOrderDiv2();
		
		m=2;
		a=new int[]{1,2,3};
		ret = x.getExpectation(m, a);
		System.out.println(Arrays.toString(ret));
		
//		m=30;
//		a=new int[]{1,2,3,4,5,6,7,8,9,10};
//		ret = x.getExpectation(m, a);
//		System.out.println(Arrays.toString(ret));
		
	}
}
